package com.gali.leetcode.day14;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @Auther: gali
 * @Date: 2022-07-30 17:31
 * @Description:
 */
public class Solution {
    /**
     * 全排列问题---回溯
     * @param nums
     * @return
     */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        for(int num:nums){
            list.add(num);
        }
        int length = nums.length;
        backtrack(length,list,lists,0);
        return lists;
    }

    private void backtrack(int length, List<Integer> list,List<List<Integer>> lists ,int first) {
        //所有数都填充完毕了
        if (first==length){
            lists.add(new ArrayList<>(list));
        }
        //动态数组
        for (int i = first; i < length; i++) {
            Collections.swap(list,first,i);
            backtrack(length,list,lists,first+1);
            Collections.swap(list,first,i);
        }
    }
}
